package com.hspedu.newData.dmsxl.树.构造二叉树;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-13 
 * @Version: 1.0
 */

public class LC95不同的二叉搜索树Ⅱ {

    public List<TreeNode> generateTrees(int n) {

        if (n==0){
            return new ArrayList<TreeNode>();
        }
        return buildTree(1,n+1);
    }

    public List<TreeNode> buildTree(int begin,int end){
        List<TreeNode> allTrees = new ArrayList<>();
        if (begin>=end){
            allTrees.add(null);
            return allTrees;
        }
        for (int i = begin; i < end; i++) {
            List<TreeNode> leftChild = buildTree(begin,i);
            List<TreeNode> rightChild = buildTree(i+1,end);

            for (TreeNode treeNode : rightChild) {
                for (TreeNode node : leftChild) {
                    TreeNode root = new TreeNode(i);
                    root.right = treeNode;
                    root.left = node;
                    allTrees.add(root);
                }
            }
        }

        return allTrees;
    }
}
